#include <string>
using namespace std;
string& InsteadStr(const int& k, const string& str1, const string& str2, string& str3)
{
    int count = 0;
    int size_1 = str1.size();
    int size_3 = str3.size();
    int tmp = 0;
    int j = 0;
    while (tmp < size_3)
    {
        
        if (count == k)
        {
            str3 = str2;
            return str3;
        }
        if (str3[tmp] == str1[j])
        {
            if (size_1 - 1 == j)
            {
                j = 0;
                count += 1;
                continue;
            }
            else
            {
                ++tmp;
                ++j;
            }
        }
        else
            ++tmp;
    }
    str3 = "F";
    return str3;
}



//实现旧式计算器
void Calculator() //A#B@C   * + -
{
    int res = 0;
    int k = 0;
    std::string str;
    std::cin >> k;
    while (k--)
    {
        std::cin >> str;
        size_t pos = 0;
        int val = 0;
        char ch = 0;
        while (!str.empty())
        {
            if (5 == str.size())
            {
                if (str.find('*') != std::string::npos)
                {
                    pos = str.find('*');
                    std::string::iterator it = str.begin() + pos;
                    ch = '*';
                    
                    res = std::stoi(std::string(1,str[pos - 1]));
                    val = std::stoi(std::string(1, str[pos + 1]));
                    str.erase(it - 1, it + 2);
                }
                else
                {
                    ch = str[1];
                    res = std::stoi(std::string(1,str[0]));
                    val = std::stoi(std::string(1,str[2]));
                    std::string::iterator it = str.begin();
                    str.erase(it, it + 3);
                }
            }
            else if (2 == str.size())
            {
                while (str.size())
                {
                    if ('*' == str[str.size()-1] || '+' == str[str.size() - 1] || '-' == str[str.size() - 1])
                    {
                        ch = str[str.size() - 1];
                        str.erase(str.size() - 1);
                    }
                    else
                    {
                        val = std::stoi(std::string(1,str[str.size() - 1]));
                        str.erase(str.size() - 1);
                    }
                }
            }
            switch (ch)
            {
            case '*':
                res = res * val;
                break;
            case '+':
                res = res + val;
                break;
            case '-':
                res = res - val;
                break;
            default:
                break;
            }
        }
        cout << res << endl;
    }
}


//题目：O(1)时间插入、删除、获取随机元素  
//(变长数组+哈希)
class RandomizedSet {
public:
    RandomizedSet() {
        
    }
    
    bool insert(int val) {
        if(hashtable.count(val) == 0)
        {
            int size = v.size();
            hashtable[val] = size;
            v.push_back(val);
            return true;
        }
        else
        return false;
    }
    
    bool remove(int val) {
        if(hashtable.count(val) == 1)
        {
            int size = v.size();
            hashtable[v[size-1]] = hashtable[val];
            std::swap(v[hashtable[val]], v[size-1]);
            v.pop_back();
            hashtable.erase(val);
            return true;
        }
        else
        return false;
    }
    
    int getRandom() {
        int size = v.size();
        int random = rand()%size;
        return v[random];
    }
    private:
    unordered_map<int,int> hashtable;
    vector<int> v;
};


//题目：同构字符串
//(哈希)
bool isIsomorphic(string s, string t) {
        unordered_map<char,char> hashtable_1;
        unordered_map<char,char> hashtable_2;
        int size = s.size();
        for(int i = 0;i < size;++i)
        {
            int ch_1 = s[i];
            int ch_2 = t[i];
            if(hashtable_1.count(ch_1) && hashtable_1[ch_1] != ch_2)
            return false;
            if(hashtable_2.count(ch_2) && hashtable_2[ch_2] != ch_1)
            return false;
            hashtable_1[ch_1] = ch_2;
            hashtable_2[ch_2] = ch_1;
        }
        return true;
    }



//题目：单词规律
//(哈希表)
class Solution {
public:
    bool wordPattern(string pattern, string s) {
        int size_1 = pattern.size();
        int size_2 = s.size();
        int p = 0;
        int i = 0,j = 0;
        unordered_map<char,string> hashtable_1;
        unordered_map<string,char> hashtable_2;
        for(i = 0;i<size_1;++i)
        {
            string tmp;
            while(p < size_2)
            {
                if(' ' == s[p])
                {
                    ++j;
                    ++p;
                    break;
                }
                tmp.push_back(s[p++]);
            }
            char ch = pattern[i];
            if(hashtable_1.count(ch) && hashtable_1[ch] != tmp || hashtable_2.count(tmp) && hashtable_2[tmp] != ch)
            return false;
            hashtable_1[ch] = tmp;
            hashtable_2[tmp] = ch;
            tmp.clear();
        }
        if(i == j+1)
        return true;
        return false;
    }
};


//题目：回文子串
//(动态规划)
int countSubstrings(string s) {
        //动态规划
        int size = s.size();
        vector<vector<bool>> dp(size,vector<bool>(size));//如果是bool类型的vector默认值为false
        int res = 0;
        //bool judge = true;
        for(int i = size-1;i >= 0;--i)
        {
            for(int j = i;j < size;++j)
            {
                int left = i,right = j;
                if(s[left] != s[right])
                continue;
                if(++left < --right && false == dp[left][right])
                continue;
                dp[i][j] = true;
                ++res;
                
        return res;
    }

    //题目：找到字符串中所有字母异位词
    //(滑动窗口+哈希表)
    vector<int> findAnagrams(string s, string p) {
        int ch1[26] = {0};
        int ch2[26] = {0};
        vector<int> v;
        int left = 0,right = 0;
        for(const auto& ch:p)
        ch2[ch-'a']++;
        while(right < s.size())
        {
            ch1[s[right]-'a']++;
            if(right-left+1 < p.size())
            {
                ++right;
                continue;
            }
            while(right-left+1 >= p.size())
            {
                if(right-left+1 == p.size())
                {
                    bool judge = true;
                    for(int i = 0;i < 26;++i)
                    {
                        if(ch1[i] != ch2[i])
                        {
                            judge = false;
                            break;
                        }
                    }
                    if(judge)
                    v.emplace_back(left);
                    ++right;
                    break;
                }
                else
                ch1[s[left++]-'a']--;
            }
        }
        return v;
    }

    //删除排序链表中的重复元素II
    //（模拟+指针）
    ListNode* deleteDuplicates(ListNode* head) {
        if(nullptr == head)
        return nullptr;
        ListNode* new_head = new ListNode(0,head);
        ListNode* cur = new_head;
        ListNode* prev = head,*last = prev->next;
        while(last != nullptr)
        {
            //当prev与last相同时，说明又要删除的元素
            if(prev->val == last->val)
            {
                while(last != nullptr && prev->val == last->val)// 要先判断last是否为空，如果为空则不可以进行->操作
                {
                    prev = last;
                    last = last->next;
                }
                cur->next = prev->next;
                if(last != nullptr)
                {
                    prev = last;
                    last = last->next;
                }
                // else   //这里也可以不用将prev置空，因为last已经是空了，下次进入大循环会自动退出
                // prev = last = nullptr;
            }
            else
            {
                cur = prev;
                prev = last;
                last = last->next;
            }
        }
        cur = new_head->next;
        delete new_head;
        return cur;
    }


    //加一
    //空间复杂度：O(1)  返回值不计入空间复杂度
    vector<int> plusOne(vector<int>& digits) {
        int index = digits.size()-1;
        for(;index >= 0;--index)
        {
            if(digits[index] != 9)
            {
                digits[index] += 1;
                for(int i = index+1;i < digits.size();++i)
                {
                    digits[i] = 0;
                }
                return digits;
            }
        }

        //digits 中所有的元素均为 9
        vector<int> ans(digits.size()+1);
        ans[0] = 1;
        return ans;
    }